<!DOCTYPE html>
<html lang="zh-CN">
  <head hexo-theme='https://github.com/volantis-x/hexo-theme-volantis/tree/4.3.1'>
  <meta charset="utf-8">
  <!-- SEO相关 -->
  
    
  
  <!-- 渲染优化 -->
  <meta http-equiv='x-dns-prefetch-control' content='on' />
  <link rel='dns-prefetch' href='https://cdn.jsdelivr.net'>
  <link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin>
  <meta name="renderer" content="webkit">
  <meta name="force-rendering" content="webkit">
  <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
  <meta name="HandheldFriendly" content="True" >
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  
  <link rel="preload" href="/blog/css/first.css" as="style">
  

  <!-- 页面元数据 -->
  
  <title>数据结构学习笔记 - song的个人博客</title>
  
    <meta name="keywords" content="数据结构">
  

  
    <meta name="description" content="上传图片太多了就没更新，都写在笔记本上了，还是纸质笔记好看
数据结构第一章数据数据是信息的载体，是描述客观事物属性的数，字符及所有能输入导计算机中并被计算机程序识别（也就是0和1对吧）和处理的符号的集合。数据是计算机程序加工的原料">
  

  <!-- feed -->
  

  <!-- import meta -->
  
    
      <meta name="msapplication-TileColor" content="#ffffff">
    
      <meta name="msapplication-config" content="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/browserconfig.xml">
    
      <meta name="theme-color" content="#ffffff">
    
  

  <!-- link -->
  
    <link rel="shortcut icon" type='image/x-icon' href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicon.ico">
  

  <!-- import link -->
  
  
  <link rel="apple-touch-icon" sizes="180x180" href="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/apple-touch-icon.png">
  <link rel="icon" type="image/png" sizes="32x32" href="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/favicon-32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/favicon-16x16.png">
  <link rel="manifest" href="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/site.webmanifest">
  <link rel="mask-icon" href="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/safari-pinned-tab.svg" color="#5bbad5">
  <link rel="shortcut icon" href="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/favicon/favicon.ico">
  

  
    
<link rel="stylesheet" href="/blog/css/first.css">

  

  
  <link rel="stylesheet" href="/blog/css/style.css" media="print" onload="this.media='all';this.onload=null">
  <noscript><link rel="stylesheet" href="/blog/css/style.css"></noscript>
  

  <script id="loadcss"></script>

  
<script>
if (/*@cc_on!@*/false || (!!window.MSInputMethodContext && !!document.documentMode))
    document.write(
	'<style>'+
		'html{'+
			'overflow-x: hidden !important;'+
			'overflow-y: hidden !important;'+
		'}'+
		'.kill-ie{'+
			'text-align:center;'+
			'height: 100%;'+
			'margin-top: 15%;'+
			'margin-bottom: 5500%;'+
		'}'+
	'</style>'+
    '<div class="kill-ie">'+
        '<h1><b>抱歉，您的浏览器无法访问本站</b></h1>'+
        '<h3>微软已经于2016年终止了对 Internet Explorer (IE) 10 及更早版本的支持，<br/>'+
        '继续使用存在极大的安全隐患，请使用当代主流的浏览器进行访问。</h3><br/>'+
        '<a target="_blank" rel="noopener" href="https://www.microsoft.com/zh-cn/WindowsForBusiness/End-of-IE-support"><strong>了解详情 ></strong></a>'+
    '</div>');
</script>


<noscript>
	<style>
		html{
			overflow-x: hidden !important;
			overflow-y: hidden !important;
		}
		.kill-noscript{
			text-align:center;
			height: 100%;
			margin-top: 15%;
			margin-bottom: 5500%;
		}
	</style>
    <div class="kill-noscript">
        <h1><b>抱歉，您的浏览器无法访问本站</b></h1>
        <h3>本页面需要浏览器支持（启用）JavaScript</h3><br/>
        <a target="_blank" rel="noopener" href="https://www.baidu.com/s?wd=启用JavaScript"><strong>了解详情 ></strong></a>
    </div>
</noscript>

</head>

  <body>
    

<header id="l_header" class="l_header auto shadow blur show" style='opacity: 0' >
  <div class='container'>
  <div id='wrapper'>
    <div class='nav-sub'>
      <p class="title"></p>
      <ul class='switcher nav-list-h m-phone' id="pjax-header-nav-list">
        <li><a id="s-comment" class="fas fa-comments fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
          <li><a id="s-toc" class="s-toc fas fa-list fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
      </ul>
    </div>
		<div class="nav-main">
      
        
        <a class="title flat-box" target="_self" href='/blog/'>
          
            <img no-lazy class='logo' src='https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/blog/Logo-NavBar@3x.png'/>
          
          
          
        </a>
      

			<div class='menu navigation'>
				<ul class='nav-list-h m-pc'>
          
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/blog/
                  
                  
                  
                    id="blog"
                  >
                  <i class='fas fa-rss fa-fw'></i>博客
                </a>
                
              </li>
            
          
          
				</ul>
			</div>

      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <i class="icon fas fa-search fa-fw"></i>
          <input type="text" class="input u-search-input" placeholder="Search..." />
        </form>
      </div>

			<ul class='switcher nav-list-h m-phone'>
				
					<li><a class="s-search fas fa-search fa-fw" target="_self" href='javascript:void(0)'></a></li>
				
				<li>
          <a class="s-menu fas fa-bars fa-fw" target="_self" href='javascript:void(0)'></a>
          <ul class="menu-phone list-v navigation white-box">
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/blog/
                  
                  
                  
                    id="blog"
                  >
                  <i class='fas fa-rss fa-fw'></i>博客
                </a>
                
              </li>
            
          
            
          </ul>
        </li>
			</ul>
		</div>
	</div>
  </div>
</header>

    <div id="l_body">
      <div id="l_cover">
  
    
        <div id="full" class='cover-wrapper py dock' style="display: none;">
          
            <div class='cover-bg lazyload placeholder' data-bg="https://bing.ioliu.cn/v1/rand?w=1920&h=1200"></div>
          
          <div class='cover-body'>
  <div class='top'>
    
    
      <p class="title">song的个人博客</p>
    
    
  </div>
  <div class='bottom'>
    <div class='menu navigation'>
      <div class='list-h'>
        
          
            <a href="/blog/v4/getting-started/"
              
              
              id="blogv4getting-started">
              <img src='https://cdn.jsdelivr.net/gh/twitter/twemoji@13.0/assets/svg/1f5c3.svg'><p>文档</p>
            </a>
          
            <a href="/blog/faqs/"
              
              
              id="blogfaqs">
              <img src='https://cdn.jsdelivr.net/gh/twitter/twemoji@13.0/assets/svg/1f516.svg'><p>帮助</p>
            </a>
          
            <a href="/blog/examples/"
              
              
              id="blogexamples">
              <img src='https://cdn.jsdelivr.net/gh/twitter/twemoji@13.0/assets/svg/1f396.svg'><p>示例</p>
            </a>
          
            <a href="/blog/contributors/"
              
              
              id="blogcontributors">
              <img src='https://cdn.jsdelivr.net/gh/twitter/twemoji@13.0/assets/svg/1f389.svg'><p>社区</p>
            </a>
          
            <a href="/blog/archives/"
              
              
              id="blogarchives">
              <img src='https://cdn.jsdelivr.net/gh/twitter/twemoji@13.0/assets/svg/1f4f0.svg'><p>博客</p>
            </a>
          
            <a target="_blank" rel="noopener" href="https://github.com/volantis-x/hexo-theme-volantis/"
              
              
              id="https:githubcomvolantis-xhexo-theme-volantis">
              <img src='https://cdn.jsdelivr.net/gh/twitter/twemoji@13.0/assets/svg/1f9ec.svg'><p>源码</p>
            </a>
          
        
      </div>
    </div>
  </div>
</div>

          <div id="scroll-down" style="display: none;"><i class="fa fa-chevron-down scroll-down-effects"></i></div>
        </div>
    
  
  </div>

      <div id="safearea">
        <div class="body-wrapper" id="pjax-container">
          

<div class='l_main'>
  <article class="article post white-box reveal md shadow article-type-py" id="py" itemscope itemprop="blogPost">
  


  
    <div class='headimg-div'>
      <a class='headimg-a'>
        <img class='headimg' src='https://z3.ax1x.com/2021/10/30/5xbck9.png'/>
      </a>
    </div>
  
  <div class="article-meta" id="top">
    
    
    
      <h1 class="title">
        数据结构学习笔记
      </h1>
      <div class='new-meta-box'>
        
          
            
<div class='new-meta-item author'>
  <a class='author' href="/" rel="nofollow">
    <img no-lazy src="">
    <p>请设置文章作者</p>
  </a>
</div>

          
        
          
            
  <div class='new-meta-item category'>
    <a class='notlink'>
      <i class="fas fa-folder-open fa-fw" aria-hidden="true"></i>
      <a class="category-link" href="/blog/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
    </a>
  </div>


          
        
          
            <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt fa-fw" aria-hidden="true"></i>
    <p>发布于：2021年6月13日</p>
  </a>
</div>

          
        
          
            
  <div class="new-meta-item browse leancloud">
    <a class='notlink'>
      
      <div id="lc-pv" data-title="数据结构学习笔记" data-path="/blog/javashuju.html">
        <i class="fas fa-eye fa-fw" aria-hidden="true"></i>
        <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span>
        次浏览
      </div>
    </a>
  </div>


          
        
      </div>
    
  </div>


  
  
  <p>上传图片太多了就没更新，都写在笔记本上了，还是纸质笔记好看</p>
<h3 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h3><h4 id="第一章"><a href="#第一章" class="headerlink" title="第一章"></a>第一章</h4><h5 id="数据"><a href="#数据" class="headerlink" title="数据"></a>数据</h5><p>数据是<strong>信息的载体</strong>，是描述客观事物属性的数，字符及所有<strong>能输入导计算机中并被计算机程序识别</strong>（也就是0和1对吧）和处理的符号的集合。数据是计算机程序加工的原料</p>
<span id="more"></span>

<p>数据元素，数据项</p>
<p><strong>数据元素</strong>是数据的基本单位，通常作为一个整体进行考虑和处理</p>
<p>一个数据元素可由若干<strong>数据项</strong>组成，数据项是构成数据元素的不可分割的最小单位</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMEooF.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMEooF.png" srcset=""></p>
<h5 id="数据结构-1"><a href="#数据结构-1" class="headerlink" title="数据结构"></a>数据结构</h5><p>数据结构是相互之间存在一种或多种特定关系的数据元素的集合</p>
<h5 id="数据对象"><a href="#数据对象" class="headerlink" title="数据对象"></a>数据对象</h5><p>数据对象是具有相同性质的数据元素的集合，是数据的一个子集</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMEHJJ.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMEHJJ.png" srcset=""></p>
<h5 id="数据结构的三要素"><a href="#数据结构的三要素" class="headerlink" title="数据结构的三要素"></a>数据结构的三要素</h5><h6 id="逻辑结构"><a href="#逻辑结构" class="headerlink" title="逻辑结构"></a>逻辑结构</h6><p>数据元素之间的逻辑关系是什么？</p>
<p><strong>1.集合</strong></p>
<p>各个元素同属一个集合，别无其它关系；</p>
<p><strong>2.线性结构</strong></p>
<p>数据之间是一对一的关系，除了第一个元素，所有元素都有唯一前驱，除了最后一个元素，所有的元素都有唯一后继；</p>
<p><strong>3.树形结构</strong></p>
<p>数据元素之间存在多对多的关系；</p>
<p><strong>4.图状结构</strong></p>
<p>或者叫网状结构，指的是数据元素之间存在多对多的关系</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMEbW9.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMEbW9.png" srcset=""></p>
<h6 id="物理结构（存储结构）"><a href="#物理结构（存储结构）" class="headerlink" title="物理结构（存储结构）"></a>物理结构（存储结构）</h6><p>1.<strong>顺序存储</strong></p>
<p>把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现</p>
<p>在内存中分配的是连续的空间。</p>
<p>2.<strong>链式存储</strong></p>
<p>链式存储逻辑上相邻元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。</p>
<p>各个元素之间的关系是通过指针来表示的，用指针表示下一个数据元素的存储地址</p>
<p>（所谓指针，也就是内存的地址；所谓指针变量，也就是保存了内存地址的变量）</p>
<p>3.<strong>索引存储</strong></p>
<p>采用这种方式存储，在存储元素信息的同时，还建立附加的索引表。索引表中的每项成为索引项，索引项的一般形式是（关键字，地址）。</p>
<p>索引表存储各个元素的顺序，关键字，地址</p>
<p>4.<strong>散列存储</strong></p>
<p>散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储。</p>
<p><strong>3到4的存储结构成为非链式存储</strong></p>
<h6 id="数据的运算"><a href="#数据的运算" class="headerlink" title="数据的运算"></a>数据的运算</h6><p>施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体实现步骤</p>
<h4 id="数据类型"><a href="#数据类型" class="headerlink" title="数据类型"></a>数据类型</h4><p>数据类型是一个值的集合和定义在此集合上的一组操作的总称</p>
<p>1.原子类型。其值不可再分的数据类型</p>
<p>2.结构类型。其值可以在分解为若干成分（分量）的数据类型</p>
<h4 id="抽象数据类型-Abstract-Data-Type-ADT"><a href="#抽象数据类型-Abstract-Data-Type-ADT" class="headerlink" title="抽象数据类型(Abstract Data Type,ADT)"></a>抽象数据类型(Abstract Data Type,ADT)</h4><p>是抽象数据组织及与之相关的操作。</p>
<p>当我们定义一个抽象数据类型的时候，其实就是用数学化的语言定义了数据的逻辑结构，定义运算和具体的实现无关。并不关心要采用哪种存储结构</p>
<p>定义一个ADT就是定义了数据的逻辑结构，数据的运算。也就是定义了一个数据结构</p>
<p>确定一种存储结构，就意味着在计算机中表示出数据的逻辑结构。存储结构不同，也会导致运算的具体实现不同。确定了存储结构，才能实现数据结构</p>
<h4 id="抽象数据类型如何定义？"><a href="#抽象数据类型如何定义？" class="headerlink" title="抽象数据类型如何定义？"></a>抽象数据类型如何定义？</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMEqzR.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMEqzR.png" srcset=""></p>
<h4 id="抽象数据类型如何表示和思想？"><a href="#抽象数据类型如何表示和思想？" class="headerlink" title="抽象数据类型如何表示和思想？"></a>抽象数据类型如何表示和思想？</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMVuFg.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMVuFg.png" srcset=""></p>
<h3 id="算法"><a href="#算法" class="headerlink" title="算法"></a>算法</h3><h4 id="什么是算法？"><a href="#什么是算法？" class="headerlink" title="什么是算法？"></a>什么是算法？</h4><p>算法是解决某一特定类型问题的有限运算序列，是一系列输入转换为输出的计算步骤。</p>
<h4 id="算法的特性"><a href="#算法的特性" class="headerlink" title="算法的特性"></a>算法的特性</h4><h5 id="有穷性"><a href="#有穷性" class="headerlink" title="有穷性"></a>有穷性</h5><p>：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。</p>
<p>注：算法必须是有穷的，但程序可以是无穷的。</p>
<h5 id="确定性"><a href="#确定性" class="headerlink" title="确定性"></a>确定性</h5><p>：算法中每条指令必须有确切的含义，对于<strong>相同的输入</strong>只能得出<strong>相同的输出</strong>。</p>
<h5 id="可行性"><a href="#可行性" class="headerlink" title="可行性"></a>可行性</h5><p>：算法中描述的操作都可以通过已经实现的<strong>基本运算执行有限次</strong>来实现。</p>
<h5 id="输入"><a href="#输入" class="headerlink" title="输入"></a>输入</h5><p>一个算法有<strong>零个或者多个输入</strong>，这些输入取自某个特定的对象的集合</p>
<h5 id="输出"><a href="#输出" class="headerlink" title="输出"></a>输出</h5><p>一个算法有<strong>一个或者多个输出</strong>，这些输出是与输入有着某种特定关系的量</p>
<h4 id="算法设计的基本要求，如何评价一个好的算法？算法的特性"><a href="#算法设计的基本要求，如何评价一个好的算法？算法的特性" class="headerlink" title="算法设计的基本要求，如何评价一个好的算法？算法的特性"></a>算法设计的基本要求，如何评价一个好的算法？算法的特性</h4><h5 id="正确性"><a href="#正确性" class="headerlink" title="正确性"></a>正确性</h5><p>算法应该能够正确的解决求解问题。</p>
<h5 id="可读性"><a href="#可读性" class="headerlink" title="可读性"></a>可读性</h5><p>算法应具有良好的可读性，以帮助人们理解。</p>
<p>注：算法可以用伪代码描述，甚至可以用文字描述，重要的是要”无歧义“地描述出解决问题的步骤。</p>
<h5 id="健壮性"><a href="#健壮性" class="headerlink" title="健壮性"></a>健壮性</h5><p>输入非法数据时，算法能适当的做出反应或者进行处理，而不会产生莫名其妙的输出结果。</p>
<h5 id="高效率和低存储量需求"><a href="#高效率和低存储量需求" class="headerlink" title="高效率和低存储量需求"></a>高效率和低存储量需求</h5><p>高效率就是执行速度快，时间复杂度低。</p>
<p>丢存储需求，就是不费内存空间复杂度低</p>
<p>脑图</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMVtTU.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMVtTU.png" srcset=""></p>
<h4 id="算法设计的基本要求"><a href="#算法设计的基本要求" class="headerlink" title="算法设计的基本要求"></a>算法设计的基本要求</h4><p>脑图中“好”算法的特性就是</p>
<h4 id="算法复杂度概念"><a href="#算法复杂度概念" class="headerlink" title="算法复杂度概念"></a>算法复杂度概念</h4><p>算法复杂度主要表现为时间bai复杂度和空间复杂度，同一算法其复杂度将直接影响其算法乃至程序的优劣。一般来说，算法的复杂度越低，其效率就越高。算法复杂度是衡量程序优劣及效率的重要指标。</p>
<h5 id="最坏时间复杂度"><a href="#最坏时间复杂度" class="headerlink" title="最坏时间复杂度"></a>最坏时间复杂度</h5><p>最坏情况下的时间复杂度</p>
<h5 id="平均时间复杂度"><a href="#平均时间复杂度" class="headerlink" title="平均时间复杂度"></a>平均时间复杂度</h5><p>所有输入实例等概率出现的情况下，算法的期望运行时间</p>
<h5 id="最好时间复杂度"><a href="#最好时间复杂度" class="headerlink" title="最好时间复杂度"></a>最好时间复杂度</h5><p>最好情况下的时间复杂度，一般没有参考意义，不考虑</p>
<h4 id="计算语句频度的方法"><a href="#计算语句频度的方法" class="headerlink" title="计算语句频度的方法"></a>计算语句频度的方法</h4><p>语句频度T(n)，又被称为时间频度，指的是该语句重复执行的次数。</p>
<h5 id="第一题"><a href="#第一题" class="headerlink" title="第一题"></a>第一题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">while</span>(i &lt;= n-<span class="number">1</span>)&#123;</span><br><span class="line">	k += <span class="number">10</span> * i;  <span class="comment">/*计算该语句频度*/</span></span><br><span class="line">	i++;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>while 循环了多少次，就是该语句的频度<br>while 执行一次 i 自增 1 ，当 i&gt;n-1 时退出，就是当 i=n 时退出 while ，i 一开始为 1，所以 while 总共循环了 n-1 次;<br>频度 ：n-1</strong></p>
<h5 id="第二题"><a href="#第二题" class="headerlink" title="第二题"></a>第二题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">	k += <span class="number">10</span> * i;  <span class="comment">/*计算该语句频度*/</span></span><br><span class="line">	i++;</span><br><span class="line">&#125;<span class="keyword">while</span>(i &lt;= n-<span class="number">1</span>);</span><br></pre></td></tr></table></figure>

<p><strong>循环了多少次，就是该语句的频度<br>循环体执行一次 i 自增 1 ，当 i&gt;n-1 时退出，就是当 i=n 时退出循环体，i 一开始为 1 ，所以循环体总共循环了 n-1 次;<br>频度 ：n-1</strong></p>
<h5 id="第三题"><a href="#第三题" class="headerlink" title="第三题"></a>第三题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">while</span>(i &lt;= n-<span class="number">1</span>)&#123;</span><br><span class="line">	i++;</span><br><span class="line">	k += <span class="number">10</span> * i;  <span class="comment">/*计算该语句频度*/</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>循环了多少次，就是该语句的频度<br>循环体执行一次 i 自增 1 ，当 i&gt;n-1 时退出，就是当 i=n 时退出循环体，i 一开始为 1 ，所以循环体总共循环了 n-1 次;<br>频度 ：n-1</strong></p>
<h5 id="第四题"><a href="#第四题" class="headerlink" title="第四题"></a>第四题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j = i; j&lt;=n; j++)&#123;</span><br><span class="line">		k++;    <span class="comment">/*计算该语句频度*/</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>第一层循环 n 次<br>第二层循环 n+(n-1)+(n-2)+…+2+1 = n(n+1)/2 ,所以 k++ 执行了 n(n+1)/2 次<br>频度 ：n(n+1)/2</strong></p>
<h5 id="第五题"><a href="#第五题" class="headerlink" title="第五题"></a>第五题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> n = <span class="number">100</span>;</span><br><span class="line"><span class="keyword">int</span> i = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">while</span>(n &gt;= (i+<span class="number">1</span>)*(i+<span class="number">1</span>))&#123;</span><br><span class="line">	i++;    	<span class="comment">/*计算该语句频度*/</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>循环体执行 floor(sqrt(n)) 次</strong><br>频度:<br>$$<br>循环体执行 floor(sqrt(n)) 次<br>频度: ⌊√n⌋<br>$$</p>
<h5 id="第六题"><a href="#第六题" class="headerlink" title="第六题"></a>第六题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> x = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> i,j,k;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">for</span>(i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">	<span class="keyword">for</span>(j = <span class="number">1</span>; j &lt;= i ; j++) &#123;</span><br><span class="line">		<span class="keyword">for</span>(k = <span class="number">1</span>; k &lt;= j; k++) &#123;</span><br><span class="line">			x += <span class="number">1</span>;   <span class="comment">/*计算该语句频度*/</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>第一层 n</strong><br><strong>第二层 1+2+3+4+…+n</strong><br><strong>第三层 1+(1+2)+(1+2+3)+(1+2+3+4)+…+(1+2+3+4+…+n) = n(n+1)(2n+3)/12<br>频度：n(n+1)(2n+3)/12</strong></p>
<h5 id="第七题"><a href="#第七题" class="headerlink" title="第七题"></a>第七题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">int</span> j = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">while</span>(i+j &lt;= n)&#123;</span><br><span class="line">	<span class="keyword">if</span>(i &gt; j)<span class="comment">/*计算该语句频度*/</span> j++;</span><br><span class="line">	<span class="keyword">else</span> i++;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>注意：if 语句不管真假都会判断一次，所以循环了多少次就判断了多少次 if 语句<br>当 i+j=n+1 时退出循环<br>所以循环次数为 (n+1)-1 = n<br>所以频度为 n</strong></p>
<h5 id="第八题"><a href="#第八题" class="headerlink" title="第八题"></a>第八题</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> x = <span class="number">91</span>;</span><br><span class="line"><span class="keyword">int</span> y = <span class="number">100</span>;</span><br><span class="line"><span class="keyword">while</span>(y &gt; <span class="number">0</span>)&#123;</span><br><span class="line">	<span class="keyword">if</span>(x &gt; <span class="number">100</span>)&#123;  <span class="comment">/*计算该判断语句频度*/</span></span><br><span class="line">		x -= <span class="number">10</span>;</span><br><span class="line">		y--;</span><br><span class="line">	&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">		x++;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>看 while 循环体中的 if 语句频度就看 while 循环次数<br>开始 x=91 ,循环了 10 次，每次都执行 else ，直到 x=101<br>当 x=101，循环了 1 次，if 条件成立，x 又变成了 91 ，而 y=99;<br>while 循环还没退出之前都是按照这规律循环，直到 y=0 退出 while ，一共重复了 100 遍上面的规律，每次 11 次循环，<br>所以该语句频度为 100*11 = 1100</strong></p>
<h5 id="注意"><a href="#注意" class="headerlink" title="注意"></a>注意</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> k = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n ;i++)&#123;  <span class="comment">//(1)</span></span><br><span class="line">	k++;     <span class="comment">//(2)</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>(1)语句频度是n+1</p>
<p><strong>i 变量在第一个 for 循环中，从取 i = 0 开始执行，直到i=n时为止，至此，i 执行了n次。加上最后i=n+1跳出循环的判断，故，频度共n+1 次；</strong></p>
<p>(2)语句频度是n</p>
<p><strong>当 i = n+1时跳出循环，所以里面的循环体一共执行了 n 次0</strong></p>
<h4 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h4><p><strong>简单的说，就是保留语句频度的最高次幂，并且把系数去掉。</strong></p>
<p> <strong>如T(n)=2n2+n+1=O(n2)</strong></p>
<p>注意：是取最高次幂，去掉系数</p>
<p>乘法规则和乘法规则</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMVWfH.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMVWfH.png" srcset=""></p>
<p>常用判断的幂次数，常用到的数量级</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMV70f.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMV70f.png" srcset=""></p>
<p>要证实的话我们用洛必达法则，当n趋近无穷大时，增长的速度谁更大</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMVqAS.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMVqAS.png" srcset=""></p>
<p>可以发现问题复杂度越大，O(1)这种算法随着问题的越来越复杂，他的时间复杂度是不会变的，所以这种算法更好</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMZLb6.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMZLb6.png" srcset=""></p>
<p>嵌套算法</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMeoo8.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMeoo8.png" srcset=""></p>
<p>习题三：</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMebWQ.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMebWQ.png" srcset=""></p>
<p>习题四：</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMeXyn.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMeXyn.png" srcset=""></p>
<p>总结：</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMexe0.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMexe0.png" srcset=""></p>
<p>脑图：</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMmCYF.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMmCYF.png" srcset=""></p>
<h3 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h3><h4 id="线性表的概念"><a href="#线性表的概念" class="headerlink" title="线性表的概念"></a>线性表的概念</h4><p>线性表是具有相同数据类型的n  ( n&gt;0 ) 个<strong>数据元素</strong>的<strong>有限序列</strong>，其中n为表长，当n=0时线性表是一个空壳。若用L命名线性表，则一般表示为</p>
<p>L=（a1，a2，…，ai，ai+1，…，an）</p>
<p>每个元素所占用的空间一样大</p>
<p>ai是线性表的第“i”个元素线性表中的位序，注意：** **</p>
<p>a1是表头元素；an是表尾元素。</p>
<p>除了第一个元素外，每个元素有且仅有一个直接前驱；除了最后一个元素外，每个元素有且仅有一个直接后继。</p>
<h4 id="线性表基本操作"><a href="#线性表基本操作" class="headerlink" title="线性表基本操作"></a>线性表基本操作</h4><h6 id="InitList-amp-L-：初始化表。"><a href="#InitList-amp-L-：初始化表。" class="headerlink" title="InitList(&amp;L)：初始化表。"></a>InitList(&amp;L)：初始化表。</h6><p>构造一个空的线性表L，分配内存空间。</p>
<h6 id="DestroyList-amp-L-：销毁操作。"><a href="#DestroyList-amp-L-：销毁操作。" class="headerlink" title="DestroyList(&amp;L)：销毁操作。"></a>DestroyList(&amp;L)：销毁操作。</h6><p>销毁线性表，并释放线性表L所占有的内存空间。</p>
<h6 id="ListInsert-amp-L-i-e-：插入操作"><a href="#ListInsert-amp-L-i-e-：插入操作" class="headerlink" title="ListInsert(&amp;L,i,e)：插入操作"></a>ListInsert(&amp;L,i,e)：插入操作</h6><p>插入操作。在表L中的第i个位置上插入指定元素e。</p>
<h6 id="ListDelete-amp-L-i-amp-e-：删除操作"><a href="#ListDelete-amp-L-i-amp-e-：删除操作" class="headerlink" title="ListDelete(&amp;L,i,&amp;e)：删除操作"></a>ListDelete(&amp;L,i,&amp;e)：删除操作</h6><p>删除表L中第i个位置的元素，并用e返回删除元素的值。</p>
<h6 id="LocateElem-L-e-：按值查找操作"><a href="#LocateElem-L-e-：按值查找操作" class="headerlink" title="LocateElem(L,e)：按值查找操作"></a>LocateElem(L,e)：按值查找操作</h6><p>在表L中查找具有给定关键字值的元素</p>
<h6 id="GetElem-L-i-：按位查找操作"><a href="#GetElem-L-i-：按位查找操作" class="headerlink" title="GetElem(L,i)：按位查找操作"></a>GetElem(L,i)：按位查找操作</h6><p>获取表L中第i个位置的元素的值</p>
<h6 id="其他常用操作："><a href="#其他常用操作：" class="headerlink" title="其他常用操作："></a>其他常用操作：</h6><p>Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。</p>
<p>PrintList(L)：输出操作。按前后顺序输出线性表的所有元素值。</p>
<p>Empty(L)：判断是否为空操作。若L为空表，则返回true，否则返回false。</p>
<p>Tips：对于数据的操作：创删，增删改查</p>
<p>脑图</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMmAyR.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMmAyR.png" srcset=""></p>
<h3 id="顺序表"><a href="#顺序表" class="headerlink" title="顺序表"></a>顺序表</h3><h4 id="顺序表的定义"><a href="#顺序表的定义" class="headerlink" title="顺序表的定义"></a>顺序表的定义</h4><p>顺序表–用顺序存储的方式实现线性表</p>
<p>顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系又存储单元的邻接关系来体现。</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMmew6.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMmew6.png" srcset=""></p>
<h4 id="顺序表的实现-静态分配"><a href="#顺序表的实现-静态分配" class="headerlink" title="顺序表的实现-静态分配"></a>顺序表的实现-静态分配</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMu0Ln.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMu0Ln.png" srcset=""></p>
<p>初始化一个顺序表，如果不给初始值</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMK9Ff.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMK9Ff.png" srcset=""></p>
<p>如果不初始化，可能会分配到脏数据的空间，但是一般不需要自己初始化，编译器会自己初始化，把length值设为0是必须的</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMBo7V.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMBo7V.png" srcset=""></p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMBHtU.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMBHtU.png" srcset=""></p>
<h4 id="顺序表的实现-动态分配"><a href="#顺序表的实现-动态分配" class="headerlink" title="顺序表的实现-动态分配"></a>顺序表的实现-动态分配</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMBO1J.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMBO1J.png" srcset=""></p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMBXc9.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMBXc9.png" srcset=""></p>
<p>具体的代码实现</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMBz0x.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMBz0x.png" srcset=""></p>
<p>free(p)把p指向的这一片存储空间释放掉，所以动态分配的方式时间开销大</p>
<p>注：realloc函数也可以实现以上的一系列操作，但是建议使用malloc和free更能理解背后过程</p>
<h4 id="顺序表的特点"><a href="#顺序表的特点" class="headerlink" title="顺序表的特点"></a>顺序表的特点</h4><p>1.随机访问，既可以在O(1)时间内找到第i个元素</p>
<p>2.存储密度高，每个节点只存储数据元素  （链式存储还需要存放元素地址）</p>
<p>3.扩展容量不方便（即便采用动态分配，拓展长度的时间复杂度也比较高）</p>
<p>4.插入，删除操作不方便，需要移动大量元素</p>
<p>脑图：</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDyuR.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDyuR.png" srcset=""></p>
<h3 id="顺序表的插入和删除"><a href="#顺序表的插入和删除" class="headerlink" title="顺序表的插入和删除"></a>顺序表的插入和删除</h3><h4 id="插入的代码实现和时间复杂度分析"><a href="#插入的代码实现和时间复杂度分析" class="headerlink" title="插入的代码实现和时间复杂度分析"></a>插入的代码实现和时间复杂度分析</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMriV0.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMriV0.png" srcset=""></p>
<p>如果要在第三个位置插入元素，所有后面的元素都要后移一位</p>
<p>基于静态分配来实现，数组长度length等于5</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MaxSize 10  <span class="comment">//定义最大长度</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> data[MaxSize]; <span class="comment">//用静态的数组存放数据元素</span></span><br><span class="line">    <span class="keyword">int</span> length;        <span class="comment">//顺序表当前的长度</span></span><br><span class="line">&#125;SqList;               <span class="comment">//顺序表类型的定义</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListInsert</span><span class="params">(SqList &amp;L,<span class="keyword">int</span> i,<span class="keyword">int</span> e)</span></span>&#123;  <span class="comment">//基本操作，在L的为序i处插入元素e</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> j=L.length;j&gt;=i;j--)   <span class="comment">//将第i个元素及之后的元素后移，大于等于i也就是大于等于3的话循环就会继续</span></span><br><span class="line">        L.data[j]=L.data[j<span class="number">-1</span>];     <span class="comment">//这一句一开始就把data[4]位置的数据，赋值移动到data[5]</span></span><br><span class="line">    L.data[i<span class="number">-1</span>]=e;                 <span class="comment">//在位置i处放入e</span></span><br><span class="line">    L.length++;                    <span class="comment">//长度加1</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    SqlList L;    <span class="comment">//声明一个顺序表</span></span><br><span class="line">    InitList(L);  <span class="comment">//初始化顺序表</span></span><br><span class="line">    <span class="comment">//...省略一些代码，插入几个元素</span></span><br><span class="line">    ListInsert(L,<span class="number">3</span>,<span class="number">3</span>);  <span class="comment">//往3的位置插入数据元素3</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>data[4]放到data[3]依次类推</p>
<p>注意位序i不是数组下标，位序i是从1开始的</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMrCbq.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMrCbq.png" srcset=""></p>
<p>判断插入操作是否合法</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">ListInsert</span><span class="params">(SqList &amp;L,<span class="keyword">int</span> i,<span class="keyword">int</span> e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(i&lt;<span class="number">1</span>||i&gt;L.length+<span class="number">1</span>)        <span class="comment">//判断i的范围是否有效</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">if</span>(L.length&gt;=MaxSize)        <span class="comment">//当前存储空间已满，不能插入</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> j=L.length;j&gt;=i;j--)  <span class="comment">//将第i个元素之后的元素后移</span></span><br><span class="line">        L.data[j]=L.data[j<span class="number">-1</span>];    <span class="comment">//for循环中的插入操作</span></span><br><span class="line">    L.data[i<span class="number">-1</span>]=e;                <span class="comment">//在i处放入e</span></span><br><span class="line">    L.length++;                   <span class="comment">//长度加1</span></span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>好的算法应该具有健壮性，能处理异常情况，并给使用者反馈</p>
<p>插入操作时间复杂度分析</p>
<p>在以上代码中只有for循环中一句操作，分析一句即可，最后计算：（首项+末项）X 项数/2</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMr9rn.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMr9rn.png" srcset=""></p>
<h4 id="删除的代码实现和时间复杂度分析"><a href="#删除的代码实现和时间复杂度分析" class="headerlink" title="删除的代码实现和时间复杂度分析"></a>删除的代码实现和时间复杂度分析</h4><p>要实现删除操作的话，首先要把数据项删除，把后面的元素向前移一位，并把length-1</p>
<p>ListDelete(&amp;L,i,e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMrpKs.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMrpKs.png" srcset=""></p>
<p>e=L.data[i-1]  ；这句会把要删除的元素复制到e这个变量所对应的内存区域当中，</p>
<p>接下来会执行一个循环，把后面的元素往前移一位</p>
<p>最后length的值减1</p>
<p>然后返回true；</p>
<p>值得注意的是，我们定义的&amp;e这个变量是一个应用类型的变量</p>
<p>加了&amp;引用符号，其实和下面int e = -1定义的是同一份数据，如果没有加&amp;，处理的e是原来的复制，在内存中是两份不同的数据</p>
<p>删除操作的时间复杂度分析</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDzvj.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDzvj.png" srcset=""></p>
<p>总结脑图</p>
<p>位序是从1开始的</p>
<p>数组下标是从0开始的</p>
<p>插入操作移动是从最后一个元素开始往后移动</p>
<p>删除操作是从删除元素的后一个元素开始往前移动</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDx2Q.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDx2Q.png" srcset=""></p>
<h3 id="顺序表的查找操作"><a href="#顺序表的查找操作" class="headerlink" title="顺序表的查找操作"></a>顺序表的查找操作</h3><h4 id="按位查找和时间复杂度"><a href="#按位查找和时间复杂度" class="headerlink" title="按位查找和时间复杂度"></a>按位查找和时间复杂度</h4><p>GetElemt(L,i);  按位查找操作。获取表L中第i个位置的元素的值。</p>
<p>如果这个表是用顺序表的方式实现，并且用静态分配的方式实现</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MaxSize 10          <span class="comment">//定义最大长度</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">	ElemType data[MaxSize];  <span class="comment">//用静态的“数组”存放数据元素</span></span><br><span class="line">	<span class="keyword">int</span> length;              <span class="comment">//顺序表当前长度</span></span><br><span class="line">&#125;SqList;                     <span class="comment">//顺序表的类型定义(静态分配)</span></span><br></pre></td></tr></table></figure>

<p>那么实现的方式也非常简单</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ElemType <span class="title">GetElem</span><span class="params">(SqList l,<span class="keyword">int</span> i)</span></span>&#123;  <span class="comment">//返回值要和表的数据类型相同</span></span><br><span class="line">    <span class="keyword">return</span> L.data[i<span class="number">-1</span>];     <span class="comment">//这个i要减一是因为位序是从1开始的</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>如果用动态分配的方式来实现顺序表的话</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> InitSize 10     <span class="comment">//顺序表的初始长度</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    ElemType *data;     <span class="comment">//指示动态分配数组的指针</span></span><br><span class="line">    <span class="keyword">int</span> MaxSize;        <span class="comment">//顺序表的最大容量</span></span><br><span class="line">    <span class="keyword">int</span> length;         <span class="comment">//顺序表当前的长度 </span></span><br><span class="line">&#125;SeqList;               <span class="comment">//顺序表的类型定义（动态分配方式）  </span></span><br></pre></td></tr></table></figure>

<p>*data这个指针指向的其实是顺序表中的第一个数据元素</p>
<p>指针指向了malloc申请的一整片内存空间的起始地址</p>
<p><strong>顺序表按位查找的代码和时间复杂度</strong></p>
<p>存储这个顺序表所需要的内存空间是通过malloc这个函数申请的一整片的内存空间</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ElemType <span class="title">GetElem</span><span class="params">(SeqList L,<span class="keyword">int</span> i)</span></span>&#123;  <span class="comment">//和访问普通的数组一样的方法</span></span><br><span class="line">    <span class="keyword">return</span> L.data[i<span class="number">-1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>没有循环操作，时间复杂度是O(1)。这也是顺序表”随机存取”的特性</strong></p>
<p><strong>能实现“随机存取”的特性，必须这些元素在内存中是连续的，并且数据类型相同</strong></p>
<p>指针对应的内存地址</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDv8g.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDv8g.png" srcset=""></p>
<p>所以回顾一下为什么动态分配方式malloc方式申请内存空间要把指针强制转换为你的数据类型</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDjPS.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDjPS.png" srcset=""></p>
<h4 id="按值查找和时间复杂度"><a href="#按值查找和时间复杂度" class="headerlink" title="按值查找和时间复杂度"></a>按值查找和时间复杂度</h4><p>LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> InitSize 10    <span class="comment">//顺序表的初始长度</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    ElemType *data;    <span class="comment">//指示动态分配的指针</span></span><br><span class="line">    <span class="keyword">int</span> MaxSize;       <span class="comment">//顺序表的最大容量</span></span><br><span class="line">    <span class="keyword">int</span> length;        <span class="comment">//顺序表当前长度</span></span><br><span class="line">&#125;SeqList;              <span class="comment">//顺序表的类型定义(动态分配)</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//在顺序表L中查找第一个元素值等于e的元素，并返回其位序</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">LocateElem</span><span class="params">(SeqList L,ElemType e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;L.length;i++)</span><br><span class="line">        <span class="keyword">if</span>(L.data[i]==e)</span><br><span class="line">            <span class="keyword">return</span> i+<span class="number">1</span>;   <span class="comment">//数组下标位i的元素值等于e，返回其位序i+1</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;             <span class="comment">//退出循环，说明查找失败</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>基本数据类型：int，char，double，float，只需要用“==”比较就行了</p>
<p>例子：</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDO58.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDO58.png" srcset=""></p>
<p>如果要比较更复杂的类型，比如结构类型呢？</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDLUf.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDLUf.png" srcset=""></p>
<p><strong>代码tips</strong></p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDqVP.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDqVP.png" srcset=""></p>
<p><strong>按值查找时间复杂度</strong></p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDHbt.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDHbt.png" srcset=""></p>
<h4 id="总结脑图"><a href="#总结脑图" class="headerlink" title="总结脑图"></a>总结脑图</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMD7DI.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMD7DI.png" srcset=""></p>
<h3 id="单链表"><a href="#单链表" class="headerlink" title="单链表"></a>单链表</h3><p><img src="https://z3.ax1x.com/2021/11/06/IMDTKA.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDTKA.png" srcset=""></p>
<h4 id="什么是单链表"><a href="#什么是单链表" class="headerlink" title="什么是单链表"></a>什么是单链表</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMDIvd.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDIvd.png" srcset=""></p>
<p>单链表一个节点包含了元素和指向下一个元素的指针，由于只包含一个指针，所有叫做单链表</p>
<h4 id="单链表和顺序表的对比"><a href="#单链表和顺序表的对比" class="headerlink" title="单链表和顺序表的对比"></a>单链表和顺序表的对比</h4><p>顺序表(顺序存储)</p>
<p>优点：可随机存取，存储密度高</p>
<p>缺点：要求大片的连续空间，改变容量不方便</p>
<p>单链表</p>
<p>优点：不要求大片连续空间，改变容量方便</p>
<p>缺点：不可随机存取，要耗费一定空间存放指针</p>
<h4 id="用代码实现单链表"><a href="#用代码实现单链表" class="headerlink" title="用代码实现单链表"></a>用代码实现单链表</h4><p>用代码定义一个节点</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">LNode</span>&#123;</span>       <span class="comment">//定义单链表节点类型  LNode:节点</span></span><br><span class="line">    ElemType data;  <span class="comment">//每个节点存放一个数据元素   data：数据域</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">LNode</span> *<span class="title">next</span>;</span>   <span class="comment">//指针指向下一个节点  next:指针域</span></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p><img src="https://z3.ax1x.com/2021/11/06/IMD5gH.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMD5gH.png" srcset=""></p>
<p>用malloc函数申请下一个节点的内存地址，再用*p指针指向它</p>
<p>typedef关键字的用法</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMD48e.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMD48e.png" srcset=""></p>
<p>上面是用typedef关键字定义的单链表，下面是不用typedef关键字定义的，两种是等同的关系</p>
<p>例子：函数是从链表L中把第i个元素取出来，返回一个节点</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDhCD.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDhCD.png" srcset=""></p>
<h4 id="不带头节点的单链表"><a href="#不带头节点的单链表" class="headerlink" title="不带头节点的单链表"></a>不带头节点的单链表</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMDW4O.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDW4O.png" srcset=""></p>
<p>注意：初始化一个空的单链表中，参数LinkList &amp;L传入指针变量的时候传入的是它的引用，</p>
<h4 id="带头节点的单链表"><a href="#带头节点的单链表" class="headerlink" title="带头节点的单链表"></a>带头节点的单链表</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMDRUK.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDRUK.png" srcset=""></p>
<p>这个头节点是不存任何数据的，只是为了我们更方便的做一些操作</p>
<h4 id="对比"><a href="#对比" class="headerlink" title="对比"></a>对比</h4><p>如果不带头节点，那么头指针L所指向的下一个节点就是实际存放数据的节点。</p>
<p>带头节点的话，那么头指针L它所指向的这个节点把它成称为头节点，它是不存放元素的，只有它的下一个节点才会用于存放数据。</p>
<h4 id="总结脑图-1"><a href="#总结脑图-1" class="headerlink" title="总结脑图"></a>总结脑图</h4><p><img src="https://z3.ax1x.com/2021/11/06/IMD2E6.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMD2E6.png" srcset=""></p>
<h3 id="单链表的插入和删除"><a href="#单链表的插入和删除" class="headerlink" title="单链表的插入和删除"></a>单链表的插入和删除</h3><p><img src="https://z3.ax1x.com/2021/11/06/IMDDgJ.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDDgJ.png" srcset=""></p>
<h4 id="按位序插入-带头节点"><a href="#按位序插入-带头节点" class="headerlink" title="按位序插入(带头节点)"></a>按位序插入(带头节点)</h4><p>比如我们要往第2个位置插入元素，就要通过malloc函数申请内存区域，写入e元素，再修改指针</p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMDrv9.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDrv9.png" srcset=""></p>
<p>如果是要插入第1个位置怎么办？这就体现出带头节点的好处了，其实和上面一样</p>
<p>头节点我们可以把它看作是第0个节点。</p>
<p><strong>代码实现，如果插入在表头</strong></p>
<img src="https://z3.ax1x.com/2021/11/06/IMDcHx.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMDcHx.png" srcset="" style="zoom:150%;" />

<p>j&lt;i-1这句的条件不满足所以直接跳过循环。</p>
<p>然后直接到下面LNode这句：</p>
<p>1.malloc函数申请内存空间。</p>
<p>2.往申请的内存空间中存入元素e。</p>
<p>3.令s的指针指向p指针指向的地址，也就是让s的指针指向第1个元素a1。</p>
<p>4.再将头节点指针指向s。</p>
<p><strong>最好的时间复杂度就是O(1)</strong></p>
<p><strong>另一种情况，插入在表中：</strong></p>
<p><img src="https://z3.ax1x.com/2021/11/06/IMD6D1.png" class="lazyload" data-srcset="https://z3.ax1x.com/2021/11/06/IMD6D1.png" srcset=""></p>
<p><strong>插入在表尾的情况：</strong></p>

  
  
  
  

  
    <div class="prev-next">
      
        <a class='prev' href='/blog/javaleet.html'>
          <p class='title'><i class="fas fa-chevron-left" aria-hidden="true"></i>leetcode第一题</p>
          <p class='content'>第一题：两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一...</p>
        </a>
      
      
        <a class='next' href='/blog/javaidea.html'>
          <p class='title'>IDEA2021安装和破解<i class="fas fa-chevron-right" aria-hidden="true"></i></p>
          <p class='content'>时隔多天又来写blog了
电脑里的IDEA还是旧版本，现在已经更新到2021了，新版本也多了很多新特性


安装还是依旧是熟悉的步骤
双击打开后选择免费使用30天，先新建个项目，当然不新建也是可...</p>
        </a>
      
    </div>
  
</article>


  

  <article class="post white-box reveal shadow" id="comments">
    <p ct><i class='fas fa-comments'></i> 评论</p>
    
    <div id="valine_container" class="valine_thread">
  <i class="fas fa-cog fa-spin fa-fw fa-2x"></i>
</div>

  </article>






</div>
<aside class='l_side'>
  
  
    
    



  <section class="widget toc-wrapper shadow desktop mobile" id="toc-div" >
    
  <header>
    
      <i class="fas fa-list fa-fw" aria-hidden="true"></i><span class='name'>本文目录</span>
    
  </header>


    <div class='content'>
        <ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-text">数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%AC%E4%B8%80%E7%AB%A0"><span class="toc-text">第一章</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE"><span class="toc-text">数据</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-1"><span class="toc-text">数据结构</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E5%AF%B9%E8%B1%A1"><span class="toc-text">数据对象</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9A%84%E4%B8%89%E8%A6%81%E7%B4%A0"><span class="toc-text">数据结构的三要素</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B"><span class="toc-text">数据类型</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B-Abstract-Data-Type-ADT"><span class="toc-text">抽象数据类型(Abstract Data Type,ADT)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E5%A6%82%E4%BD%95%E5%AE%9A%E4%B9%89%EF%BC%9F"><span class="toc-text">抽象数据类型如何定义？</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E5%A6%82%E4%BD%95%E8%A1%A8%E7%A4%BA%E5%92%8C%E6%80%9D%E6%83%B3%EF%BC%9F"><span class="toc-text">抽象数据类型如何表示和思想？</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AE%97%E6%B3%95"><span class="toc-text">算法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E7%AE%97%E6%B3%95%EF%BC%9F"><span class="toc-text">什么是算法？</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E7%9A%84%E7%89%B9%E6%80%A7"><span class="toc-text">算法的特性</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%9C%89%E7%A9%B7%E6%80%A7"><span class="toc-text">有穷性</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%A1%AE%E5%AE%9A%E6%80%A7"><span class="toc-text">确定性</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E5%8F%AF%E8%A1%8C%E6%80%A7"><span class="toc-text">可行性</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E8%BE%93%E5%85%A5"><span class="toc-text">输入</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E8%BE%93%E5%87%BA"><span class="toc-text">输出</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E7%9A%84%E5%9F%BA%E6%9C%AC%E8%A6%81%E6%B1%82%EF%BC%8C%E5%A6%82%E4%BD%95%E8%AF%84%E4%BB%B7%E4%B8%80%E4%B8%AA%E5%A5%BD%E7%9A%84%E7%AE%97%E6%B3%95%EF%BC%9F%E7%AE%97%E6%B3%95%E7%9A%84%E7%89%B9%E6%80%A7"><span class="toc-text">算法设计的基本要求，如何评价一个好的算法？算法的特性</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%AD%A3%E7%A1%AE%E6%80%A7"><span class="toc-text">正确性</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E5%8F%AF%E8%AF%BB%E6%80%A7"><span class="toc-text">可读性</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E5%81%A5%E5%A3%AE%E6%80%A7"><span class="toc-text">健壮性</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E9%AB%98%E6%95%88%E7%8E%87%E5%92%8C%E4%BD%8E%E5%AD%98%E5%82%A8%E9%87%8F%E9%9C%80%E6%B1%82"><span class="toc-text">高效率和低存储量需求</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E7%9A%84%E5%9F%BA%E6%9C%AC%E8%A6%81%E6%B1%82"><span class="toc-text">算法设计的基本要求</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%A6%82%E5%BF%B5"><span class="toc-text">算法复杂度概念</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%9C%80%E5%9D%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">最坏时间复杂度</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E5%B9%B3%E5%9D%87%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">平均时间复杂度</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%9C%80%E5%A5%BD%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">最好时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%AE%A1%E7%AE%97%E8%AF%AD%E5%8F%A5%E9%A2%91%E5%BA%A6%E7%9A%84%E6%96%B9%E6%B3%95"><span class="toc-text">计算语句频度的方法</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E4%B8%80%E9%A2%98"><span class="toc-text">第一题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E4%BA%8C%E9%A2%98"><span class="toc-text">第二题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E4%B8%89%E9%A2%98"><span class="toc-text">第三题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E5%9B%9B%E9%A2%98"><span class="toc-text">第四题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E4%BA%94%E9%A2%98"><span class="toc-text">第五题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E5%85%AD%E9%A2%98"><span class="toc-text">第六题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E4%B8%83%E9%A2%98"><span class="toc-text">第七题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E7%AC%AC%E5%85%AB%E9%A2%98"><span class="toc-text">第八题</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E6%B3%A8%E6%84%8F"><span class="toc-text">注意</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8"><span class="toc-text">线性表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E6%A6%82%E5%BF%B5"><span class="toc-text">线性表的概念</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C"><span class="toc-text">线性表基本操作</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8"><span class="toc-text">顺序表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-text">顺序表的定义</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0-%E9%9D%99%E6%80%81%E5%88%86%E9%85%8D"><span class="toc-text">顺序表的实现-静态分配</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0-%E5%8A%A8%E6%80%81%E5%88%86%E9%85%8D"><span class="toc-text">顺序表的实现-动态分配</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E7%89%B9%E7%82%B9"><span class="toc-text">顺序表的特点</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E6%8F%92%E5%85%A5%E5%92%8C%E5%88%A0%E9%99%A4"><span class="toc-text">顺序表的插入和删除</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E7%9A%84%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0%E5%92%8C%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-text">插入的代码实现和时间复杂度分析</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%88%A0%E9%99%A4%E7%9A%84%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0%E5%92%8C%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-text">删除的代码实现和时间复杂度分析</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E6%9F%A5%E6%89%BE%E6%93%8D%E4%BD%9C"><span class="toc-text">顺序表的查找操作</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8C%89%E4%BD%8D%E6%9F%A5%E6%89%BE%E5%92%8C%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">按位查找和时间复杂度</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8C%89%E5%80%BC%E6%9F%A5%E6%89%BE%E5%92%8C%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">按值查找和时间复杂度</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%BB%E7%BB%93%E8%84%91%E5%9B%BE"><span class="toc-text">总结脑图</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">单链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">什么是单链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%8D%95%E9%93%BE%E8%A1%A8%E5%92%8C%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AF%B9%E6%AF%94"><span class="toc-text">单链表和顺序表的对比</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%94%A8%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">用代码实现单链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8D%E5%B8%A6%E5%A4%B4%E8%8A%82%E7%82%B9%E7%9A%84%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">不带头节点的单链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%B8%A6%E5%A4%B4%E8%8A%82%E7%82%B9%E7%9A%84%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">带头节点的单链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AF%B9%E6%AF%94"><span class="toc-text">对比</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%BB%E7%BB%93%E8%84%91%E5%9B%BE-1"><span class="toc-text">总结脑图</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E6%8F%92%E5%85%A5%E5%92%8C%E5%88%A0%E9%99%A4"><span class="toc-text">单链表的插入和删除</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8C%89%E4%BD%8D%E5%BA%8F%E6%8F%92%E5%85%A5-%E5%B8%A6%E5%A4%B4%E8%8A%82%E7%82%B9"><span class="toc-text">按位序插入(带头节点)</span></a></li></ol></li></ol>
    </div>
  </section>


  


</aside>



		  
		  <!--此文件用来存放一些不方便取值的变量-->
<!--思路大概是将值藏到重加载的区域内-->

<script>
  window.pdata={}
  pdata.ispage=false;
  pdata.postTitle="";
  pdata.commentPath="";
  pdata.commentPlaceholder="";
  // header 这里无论是否开启pjax都需要
  var l_header=document.getElementById("l_header");
  
  l_header.classList.add("show");
  
  
    // cover
    var cover_wrapper=document.querySelector('.cover-wrapper');
    
    cover_wrapper.id="none";
    cover_wrapper.style.display="none";
    
  
</script>

        </div>
        
  
  <footer class="footer clearfix">
    <br><br>
    
      
        <div class="aplayer-container">
          


        </div>
      
    
      
        <br>
        <div class="social-wrapper">
          
            
          
            
          
            
          
        </div>
      
    
      
        <div><p>博客内容遵循 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</a></p>
</div>
      
    
      
        
          <div><p><span id="lc-sv">本站总访问量为 <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span> 次</span> <span id="lc-uv">访客数为 <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span> 人</span></p>
</div>
        
      
    
      
        本站使用
        <a href="https://github.com/volantis-x/hexo-theme-volantis/tree/4.3.1" target="_blank" class="codename">Volantis</a>
        作为主题
      
    
      
        <div class='copyright'>
        <p><a href="/">Copyright © 2017-2020 XXX</a></p>

        </div>
      
    
  </footer>


        <a id="s-top" class="fas fa-arrow-up fa-fw" href="javascript:void(0)"></a>
      </div>
    </div>
    <div>
      <script>
/************这个文件存放不需要重载的全局变量和全局函数*********/
window.volantis={};
window.volantis.loadcss=document.getElementById("loadcss");
/******************** Pjax ********************************/
function VPjax(){
	this.list=[] // 存放回调函数
	this.start=()=>{
	  for(var i=0;i<this.list.length;i++){
		this.list[i].run();
	  }
	}
	this.push=(fn,name)=>{
		var f=new PjaxItem(fn,name);
		this.list.push(f);
	}
	// 构造一个可以run的对象
	function PjaxItem(fn,name){
		// 函数名称
		this.name = name || fn.name
		// run方法
		this.run=()=>{
			fn()
		}
	}
}
volantis.pjax={}
volantis.pjax.method={
	complete: new VPjax(),
	error: new VPjax(),
	send: new VPjax()
}
volantis.pjax={
	...volantis.pjax,
	push: volantis.pjax.method.complete.push,
	error: volantis.pjax.method.error.push,
	send: volantis.pjax.method.send.push
}
/********************脚本懒加载函数********************************/
// 已经加入了setTimeout
function loadScript(src, cb) {
	setTimeout(function() {
		var HEAD = document.getElementsByTagName('head')[0] || document.documentElement;
		var script = document.createElement('script');
		script.setAttribute('type','text/javascript');
		if (cb) script.onload = cb;
		script.setAttribute('src', src);
		HEAD.appendChild(script);
	});
}
//https://github.com/filamentgroup/loadCSS
var loadCSS = function( href, before, media, attributes ){
	var doc = window.document;
	var ss = doc.createElement( "link" );
	var ref;
	if( before ){
		ref = before;
	}
	else {
		var refs = ( doc.body || doc.getElementsByTagName( "head" )[ 0 ] ).childNodes;
		ref = refs[ refs.length - 1];
	}
	var sheets = doc.styleSheets;
	if( attributes ){
		for( var attributeName in attributes ){
			if( attributes.hasOwnProperty( attributeName ) ){
				ss.setAttribute( attributeName, attributes[attributeName] );
			}
		}
	}
	ss.rel = "stylesheet";
	ss.href = href;
	ss.media = "only x";
	function ready( cb ){
		if( doc.body ){
			return cb();
		}
		setTimeout(function(){
			ready( cb );
		});
	}
	ready( function(){
		ref.parentNode.insertBefore( ss, ( before ? ref : ref.nextSibling ) );
	});
	var onloadcssdefined = function( cb ){
		var resolvedHref = ss.href;
		var i = sheets.length;
		while( i-- ){
			if( sheets[ i ].href === resolvedHref ){
				return cb();
			}
		}
		setTimeout(function() {
			onloadcssdefined( cb );
		});
	};
	function loadCB(){
		if( ss.addEventListener ){
			ss.removeEventListener( "load", loadCB );
		}
		ss.media = media || "all";
	}
	if( ss.addEventListener ){
		ss.addEventListener( "load", loadCB);
	}
	ss.onloadcssdefined = onloadcssdefined;
	onloadcssdefined( loadCB );
	return ss;
};
</script>
<script>
  
  loadCSS("https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14/css/all.min.css", window.volantis.loadcss);
  
  
  
  
</script>
<!-- required -->

<script src="https://cdn.jsdelivr.net/npm/jquery@3.5/dist/jquery.min.js"></script>

<script>
  function pjax_fancybox() {
    $(".md .gallery").find("img").each(function () { //渲染 fancybox
      var element = document.createElement("a"); // a 标签
      $(element).attr("class", "fancybox");
      $(element).attr("pjax-fancybox", "");  // 过滤 pjax
      $(element).attr("href", $(this).attr("src"));
      if ($(this).attr("data-original")) {
        $(element).attr("href", $(this).attr("data-original"));
      }
      $(element).attr("data-fancybox", "images");
      var caption = "";   // 描述信息
      if ($(this).attr('alt')) {  // 判断当前页面是否存在描述信息
        $(element).attr('data-caption', $(this).attr('alt'));
        caption = $(this).attr('alt');
      }
      var div = document.createElement("div");
      $(div).addClass("fancybox");
      $(this).wrap(div); // 最外层套 div ，其实主要作用还是 class 样式
      var span = document.createElement("span");
      $(span).addClass("image-caption");
      $(span).text(caption); // 加描述
      $(this).after(span);  // 再套一层描述
      $(this).wrap(element);  // 最后套 a 标签
    })
    $(".md .gallery").find("img").fancybox({
      selector: '[data-fancybox="images"]',
      hash: false,
      loop: false,
      closeClick: true,
      helpers: {
        overlay: {closeClick: true}
      },
      buttons: [
        "zoom",
        "close"
      ]
    });
  };
  function SCload_fancybox() {
    if ($(".md .gallery").find("img").length == 0) return;
    loadCSS("https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css", document.getElementById("loadcss"));
    loadScript('https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js', pjax_fancybox)
  };
  $(function () {
    SCload_fancybox();
  });
  function Pjax_SCload_fancybox(){
	if (typeof $.fancybox == "undefined") {
	 SCload_fancybox();
    } else {
	 pjax_fancybox();
    }
  }
  volantis.pjax.push(Pjax_SCload_fancybox)
  volantis.pjax.send(()=>{
      if (typeof $.fancybox != "undefined") {
        $.fancybox.close();    // 关闭弹窗
      }
  },'fancybox')
</script>


<!-- internal -->



  
  

  <div id="rightmenu-wrapper">
    <ul class="list-v rightmenu" id="rightmenu-content">
      <li class='option'>
        <a class='vlts-menu opt fix-cursor-default' id='menu-copy-text' onclick="document.execCommand('copy')"><i class='fa fa-copy fa-fw'></i>复制文本</a>
        <hr id='hr-text'>
        <a class='vlts-menu opt fix-cursor-default' id='menu-copy-href'><i class='fa fa-link fa-fw'></i>复制链接</a>
        <a class='vlts-menu opt fix-cursor-default' id='menu-open-href'><i class='fa fa-external-link-square-alt fa-fw'></i>在新标签页打开</a>
        <hr id='hr-href'>
        <a class='vlts-menu opt fix-cursor-default' id='menu-copy-src'><i class='fa fa-image fa-fw'></i>复制图片地址</a>
        <hr id='hr-src'>
      </li>
      
        <li class='navigation'>
          <a class='nav icon-only fix-cursor-default' onclick='history.back()'><i class='fa fa-arrow-left fa-fw'></i></a>
          <a class='nav icon-only fix-cursor-default' onclick='history.forward()'><i class='fa fa-arrow-right fa-fw'></i></a>
          <a class='nav icon-only fix-cursor-default' onclick='window.location.reload()'><i class='fa fa-redo fa-fw'></i></a>
          <a class='nav icon-only fix-cursor-default' href='/'><i class='fa fa-home fa-fw'></i></a>
        </li>
      
      <hr>
      
        
      
        
          <hr>
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' href=https://volantis.js.org/faqs/
        
        
        
        
          id="https:volantisjsorgfaqs"
        >
        <i class='fa fa-question fa-fw'></i> 常见问题
      </a>
    </li>
  
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' href=https://volantis.js.org/examples/
        
        
        
        
          id="https:volantisjsorgexamples"
        >
        <i class='fa fa-rss fa-fw'></i> 示例博客
      </a>
    </li>
  
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' href=https://volantis.js.org/contributors/
        
        
        
        
          id="https:volantisjsorgcontributors"
        >
        <i class='fa fa-fan fa-spin fa-fw'></i> 加入社区
      </a>
    </li>
  
        
      
        
          <hr>
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' href=https://github.com/volantis-x/volantis-docs/
        
        
        
        
          id="https:githubcomvolantis-xvolantis-docs"
        >
        <i class='fa fa-code-branch fa-fw'></i> 本站源码
      </a>
    </li>
  
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' href=https://github.com/volantis-x/hexo-theme-volantis/
        
        
        
        
          id="https:githubcomvolantis-xhexo-theme-volantis"
        >
        <i class='fa fa-code-branch fa-fw'></i> 主题源码
      </a>
    </li>
  
        
      
        
          <hr>
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' 
        
        
        
          onclick="document.execCommand('print')"
        
        >
        <i class='fa fa-print fa-fw'></i> 打印页面
      </a>
    </li>
  
        
      
        
          
    <li>
      <a class='vlts-menu fix-cursor-default ' 
        
        
        
        >
        <i class='fa fa-moon fa-fw'></i> 暗黑模式
      </a>
    </li>
  
        
      
        
      
    </ul>
  </div>

  <script>
    window.document.oncontextmenu = function (event) {
      if (event.ctrlKey) return true;
      if (/Android|webOS|BlackBerry/i.test(navigator.userAgent)) return true;
      return popMenu(event);
    };
    document.addEventListener("click", function (event) {
      var mymenu = document.getElementById('rightmenu-wrapper');
      mymenu.style.display = "none";
    });
    function popMenu(event) {
      var mymenu = document.getElementById('rightmenu-wrapper');
      var menuContent = document.getElementById('rightmenu-content');
      var screenWidth = document.documentElement.clientWidth || document.body.clientWidth;
      var screenHeight = document.documentElement.clientHeight || document.body.clientHeight;
      mymenu.style.left = event.clientX + "px"; // 获取鼠标位置
      mymenu.style.top = event.clientY + "px";
      mymenu.style.display = 'block';
      if (event.clientX * 2 > screenWidth) {
        menuContent.classList.add('left');
      } else {
        menuContent.classList.remove('left');
      }
      if (event.clientY * 2 > screenHeight) {
        menuContent.classList.add('top');
      } else {
        menuContent.classList.remove('top');
      }

      let hrText = document.getElementById('hr-text');
      let hrSrc = document.getElementById('hr-src');
      let hrHref = document.getElementById('hr-href');

      // 选中图片
      let copySrc = document.getElementById('menu-copy-src');
      if (copySrc != undefined) {
        if (event.target.currentSrc) {
          copySrc.style.display = 'block';
          copySrc.addEventListener("click", function (e) {
            copyString(event.target.currentSrc);
          },{once: true});
          hrSrc.style.display = 'block';
        } else {
          copySrc.style.display = 'none';
          hrSrc.style.display = 'none';
        }
      }

      // 选中按钮
      // 判断是不是按钮
      let href = '';
      if (event.path) {
        for (i = 0; i < event.path.length; i++) {
          if (event.path[i].href != undefined && event.path[i].href.length > 0) {
            href = event.path[i].href;
          }
        }
      }

      let copyText = document.getElementById('menu-copy-text');
      copyText.style.display = 'none';
      hrText.style.display = 'none';
      if (href.length == 0) {
        // 选中文本
        if (window.getSelection().toString()) {
          if ('' == 'true') {
            copyText.style.display = 'block';
            hrText.style.display = 'block';
          }
        }
      }

      // 在新标签页打开
      let openHref = document.getElementById('menu-open-href');
      if (openHref != undefined) {
        if (href.length > 0) {
          openHref.style.display = 'block';
          openHref.addEventListener("click", function (e) {
            window.open(href);
          },{once: true});
          hrHref.style.display = 'block';
        } else {
          openHref.style.display = 'none';
          hrHref.style.display = 'none';
        }
      }
      // 复制链接
      let copyHref = document.getElementById('menu-copy-href');
      if (copyHref != undefined) {
        if (href.length > 0) {
          copyHref.style.display = 'block';
          copyHref.addEventListener("click", function (e) {
            copyString(href);
          },{once: true});
        } else {
          copyHref.style.display = 'none';
        }
      }
      // 有音乐播放器 see: layout/_third-party/aplayer/script.ejs
      
      return false; // 该行代码确保系统自带的右键菜单不会被调出
    }
    function hideMenu() {
      document.getElementById('rightmenu-wrapper').style.display = 'none';
    }
    function copyString(str) {
      const input = document.createElement('input');
      input.setAttribute('readonly', 'readonly');
      document.body.appendChild(input);
      input.setAttribute('value', str);
      input.select();
      document.execCommand('copy');
      document.body.removeChild(input);
    }
    document.execCommand('click');
  </script>




<script>
  function loadIssuesJS() {
    if ($(".md").find(".issues-api").length == 0) return;
	
	  loadScript('/blog/js/issues.js');
	
  };
  $(function () {
    loadIssuesJS();
  });
  volantis.pjax.push(()=>{
	if (typeof IssuesAPI == "undefined") {
	  loadIssuesJS();
	}
  },"IssuesJS")
</script>



  <script defer src="https://cdn.jsdelivr.net/npm/vanilla-lazyload@17.1.0/dist/lazyload.min.js"></script>
<script>
  // https://www.npmjs.com/package/vanilla-lazyload
  // Set the options globally
  // to make LazyLoad self-initialize
  window.lazyLoadOptions = {
    elements_selector: ".lazyload",
    threshold: 0
  };
  // Listen to the initialization event
  // and get the instance of LazyLoad
  window.addEventListener(
    "LazyLoad::Initialized",
    function (event) {
      window.lazyLoadInstance = event.detail.instance;
    },
    false
  );
  document.addEventListener('DOMContentLoaded', function () {
    lazyLoadInstance.update();
  });
  document.addEventListener('pjax:complete', function () {
    lazyLoadInstance.update();
  });
</script>




  

<script>
  window.FPConfig = {
	delay: 0,
	ignoreKeywords: [],
	maxRPS: 5,
	hoverDelay: 25
  };
</script>
<script defer src="https://cdn.jsdelivr.net/gh/gijo-varghese/flying-pages@2.1.2/flying-pages.min.js"></script>











  
  
<script src="/blog/js/valine.js"></script>


<script>
  function emoji(path, idx, ext) {
    return path + "/" + path + "-" + idx + "." + ext;
  }
  var emojiMaps = {};
  for (var i = 1; i <= 54; i++) {
    emojiMaps['tieba-' + i] = emoji('tieba', i, 'png');
  }
  for (var i = 1; i <= 101; i++) {
    emojiMaps['qq-' + i] = emoji('qq', i, 'gif');
  }
  for (var i = 1; i <= 116; i++) {
    emojiMaps['aru-' + i] = emoji('aru', i, 'gif');
  }
  for (var i = 1; i <= 125; i++) {
    emojiMaps['twemoji-' + i] = emoji('twemoji', i, 'png');
  }
  for (var i = 1; i <= 4; i++) {
    emojiMaps['weibo-' + i] = emoji('weibo', i, 'png');
  }
  function pjax_valine() {
    if(!document.querySelectorAll("#valine_container")[0])return;
    let pagePlaceholder = pdata.commentPlaceholder || "快来评论吧~";
    let path = pdata.commentPath;
    if (path.length == 0) {
      let defaultPath = '';
      path = defaultPath || decodeURI(window.location.pathname);
    }
    var valine = new Valine();
    valine.init(Object.assign({"path":null,"placeholder":"快来评论吧~","appId":null,"appKey":null,"meta":["nick","mail","link"],"requiredFields":["nick","mail"],"enableQQ":true,"recordIP":false,"avatar":"robohash","pageSize":10,"lang":"zh-cn","highlight":true,"mathJax":false}, {
      el: '#valine_container',
      path: path,
      placeholder: pagePlaceholder,
      emojiCDN: 'https://cdn.jsdelivr.net/gh/volantis-x/cdn-emoji/valine/',
      emojiMaps: emojiMaps,
    }))
  }
  $(function () {
    pjax_valine();
  });
  volantis.pjax.push(pjax_valine);
</script>






  
<script src="/blog/js/app.js"></script>



<!-- optional -->

  <script>
const SearchServiceimagePath="https://cdn.jsdelivr.net/gh/volantis-x/cdn-volantis@master/img/";
const ROOT =  ("/blog/" || "/").endsWith('/') ? ("/blog/" || "/") : ("/blog//" || "/" );

$('.input.u-search-input').one('focus',function(){
	
		loadScript('/blog/js/search/hexo.js',setSearchService);
	
})

function listenSearch(){
  
    customSearch = new HexoSearch({
      imagePath: SearchServiceimagePath
    });
  
}
function setSearchService() {
	listenSearch();
	
}
</script>











  <script defer>

  const LCCounter = {
    app_id: 'u9j57bwJod4EDmXWdxrwuqQT-MdYXbMMI',
    app_key: 'jfHtEKVE24j0IVCGHbvuFClp',
    custom_api_server: '',

    // 查询存储的记录
    getRecord(Counter, url, title) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({url})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {url, title: title, times: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    },

    // 发起自增请求
    increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    },

    // 构建自增请求体
    buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "times": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    },

    // 校验是否为有效的 UV
    validUV() {
      var key = 'LeanCloudUVTimestamp';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    },

    addCount(Counter) {
      var enableIncr = '' === 'true' && window.location.hostname !== 'localhost';
      enableIncr = true;
      var getterArr = [];
      var incrArr = [];
      // 请求 PV 并自增
      var pvCtn = document.querySelector('#lc-sv');
      if (pvCtn || enableIncr) {
        var pvGetter = this.getRecord(Counter, 'http://shouyeren24.gitee.io' + '/#lc-sv', 'Visits').then((record) => {
          incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-sv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + 1;
              if (pvCtn) {
                pvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#lc-uv');
      if (uvCtn || enableIncr) {
        var uvGetter = this.getRecord(Counter, 'http://shouyeren24.gitee.io' + '/#lc-uv', 'Visitors').then((record) => {
          var vuv = this.validUV();
          vuv && incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-uv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + (vuv ? 1 : 0);
              if (uvCtn) {
                uvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(uvGetter);
      }

      // 请求文章的浏览数，如果是当前页面就自增
      var allPV = document.querySelectorAll('#lc-pv');
      if (allPV.length > 0 || enableIncr) {
        for (i = 0; i < allPV.length; i++) {
          let pv = allPV[i];
          let title = pv.getAttribute('data-title');
          var url = 'http://shouyeren24.gitee.io' + pv.getAttribute('data-path');
          if (url) {
            var viewGetter = this.getRecord(Counter, url, title).then((record) => {
              // 是当前页面就自增
              let curPath = window.location.pathname;
              if (curPath.includes('index.html')) {
                curPath = curPath.substring(0, curPath.lastIndexOf('index.html'));
              }
              if (pv.getAttribute('data-path') == curPath) {
                incrArr.push(this.buildIncrement(record.objectId));
              }
              if (pv) {
                var ele = pv.querySelector('#lc-pv #number');
                if (ele) {
                  if (pv.getAttribute('data-path') == curPath) {
                    ele.innerText = (record.times || 0) + 1;
                  } else {
                    ele.innerText = record.times || 0;
                  }
                  pv.style.display = 'inline';
                }
              }
            });
            getterArr.push(viewGetter);
          }
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && this.increment(Counter, incrArr);
        })
      }

    },


    fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': this.app_id,
            'X-LC-Key': this.app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      this.addCount(Counter);
    },

    refreshCounter() {
      var api_server = this.app_id.slice(-9) !== '-MdYXbMMI' ? this.custom_api_server : `https://${ this.app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;
      if (api_server) {
        this.fetchData(api_server);
      } else {
        fetch('https://app-router.leancloud.cn/2/route?appId=' + this.app_id)
          .then(resp => resp.json())
          .then(({api_server}) => {
            this.fetchData('https://' + api_server);
          });
      }
    }

  };

  LCCounter.refreshCounter();

  document.addEventListener('pjax:complete', function () {
    LCCounter.refreshCounter();
  });
</script>




  <script>
const rootElement = document.documentElement;
const darkModeStorageKey = "user-color-scheme";
const rootElementDarkModeAttributeName = "data-user-color-scheme";

const setLS = (k, v) => {
    localStorage.setItem(k, v);
};

const removeLS = (k) => {
    localStorage.removeItem(k);
};

const getLS = (k) => {
    return localStorage.getItem(k);
};

const getModeFromCSSMediaQuery = () => {
  return window.matchMedia("(prefers-color-scheme: dark)").matches
    ? "dark"
    : "light";
};

const resetRootDarkModeAttributeAndLS = () => {
  rootElement.removeAttribute(rootElementDarkModeAttributeName);
  removeLS(darkModeStorageKey);
};

const validColorModeKeys = {
  dark: true,
  light: true,
};

const applyCustomDarkModeSettings = (mode) => {
  const currentSetting = mode || getLS(darkModeStorageKey);

  if (currentSetting === getModeFromCSSMediaQuery()) {
    resetRootDarkModeAttributeAndLS();
  } else if (validColorModeKeys[currentSetting]) {
    rootElement.setAttribute(rootElementDarkModeAttributeName, currentSetting);
  } else {
    resetRootDarkModeAttributeAndLS();
  }
};

const invertDarkModeObj = {
  dark: "light",
  light: "dark",
};

/**
 * get target mode
 */
const toggleCustomDarkMode = () => {
  let currentSetting = getLS(darkModeStorageKey);

  if (validColorModeKeys[currentSetting]) {
    currentSetting = invertDarkModeObj[currentSetting];
  } else if (currentSetting === null) {
    currentSetting = invertDarkModeObj[getModeFromCSSMediaQuery()];
  } else {
    return;
  }
  setLS(darkModeStorageKey, currentSetting);
  return currentSetting;
};

/**
 * bind click event for toggle button
 */
var btn=$("#wrapper .toggle-mode-btn,#rightmenu-wrapper .toggle-mode-btn");
function bindToggleButton() {
    btn.on('click',(e) => {
      const mode = toggleCustomDarkMode();
      applyCustomDarkModeSettings(mode);
    });
}

applyCustomDarkModeSettings();
document.addEventListener("DOMContentLoaded", bindToggleButton);
volantis.pjax.push(bindToggleButton);
volantis.pjax.send(()=>{
	btn.unbind('click');
},'toggle-mode-btn-unbind');
</script>








<script>
function listennSidebarTOC() {
  const navItems = document.querySelectorAll(".toc li");
  if (!navItems.length) return;
  const sections = [...navItems].map((element) => {
    const link = element.querySelector(".toc-link");
    const target = document.getElementById(
      decodeURI(link.getAttribute("href")).replace("#", "")
    );
    link.addEventListener("click", (event) => {
      event.preventDefault();
      window.scrollTo({
		top: target.offsetTop + 100,
		
		behavior: "smooth"
		
	  });
    });
    return target;
  });

  function activateNavByIndex(target) {
    if (target.classList.contains("active-current")) return;

    document.querySelectorAll(".toc .active").forEach((element) => {
      element.classList.remove("active", "active-current");
    });
    target.classList.add("active", "active-current");
    let parent = target.parentNode;
    while (!parent.matches(".toc")) {
      if (parent.matches("li")) parent.classList.add("active");
      parent = parent.parentNode;
    }
  }

  function findIndex(entries) {
    let index = 0;
    let entry = entries[index];
    if (entry.boundingClientRect.top > 0) {
      index = sections.indexOf(entry.target);
      return index === 0 ? 0 : index - 1;
    }
    for (; index < entries.length; index++) {
      if (entries[index].boundingClientRect.top <= 0) {
        entry = entries[index];
      } else {
        return sections.indexOf(entry.target);
      }
    }
    return sections.indexOf(entry.target);
  }

  function createIntersectionObserver(marginTop) {
    marginTop = Math.floor(marginTop + 10000);
    let intersectionObserver = new IntersectionObserver(
      (entries, observe) => {
        let scrollHeight = document.documentElement.scrollHeight + 100;
        if (scrollHeight > marginTop) {
          observe.disconnect();
          createIntersectionObserver(scrollHeight);
          return;
        }
        let index = findIndex(entries);
        activateNavByIndex(navItems[index]);
      },
      {
        rootMargin: marginTop + "px 0px -100% 0px",
        threshold: 0,
      }
    );
    sections.forEach((element) => {
      element && intersectionObserver.observe(element);
    });
  }
  createIntersectionObserver(document.documentElement.scrollHeight);
}

document.addEventListener("DOMContentLoaded", listennSidebarTOC);
document.addEventListener("pjax:success", listennSidebarTOC);
</script>

<!-- more -->

 
	   
	    


<script src="https://cdn.jsdelivr.net/npm/pjax@0.2.8/pjax.min.js"></script>


<script>
    var pjax;
    document.addEventListener('DOMContentLoaded', function () {
      pjax = new Pjax({
        elements: 'a[href]:not([href^="#"]):not([href="javascript:void(0)"]):not([pjax-fancybox])',
        selectors: [
          "title",
          
          "#pjax-container",
          "#pjax-header-nav-list"
        ],
        cacheBust: false,   // url 地址追加时间戳，用以避免浏览器缓存
        timeout: 5000
      });
    });

    document.addEventListener('pjax:send', function (e) {
      //window.stop(); // 相当于点击了浏览器的停止按钮

      try {
        var currentUrl = window.location.pathname;
        var targetUrl = e.triggerElement.href;
        var banUrl = [""];
        if (banUrl[0] != "") {
          banUrl.forEach(item => {
            if(currentUrl.indexOf(item) != -1 || targetUrl.indexOf(item) != -1) {
              window.location.href = targetUrl;
            }
          });
        }
      } catch (error) {}

      window.subData = null; // 移除标题（用于一二级导航栏切换处）

      volantis.$switcher.removeClass('active'); // 关闭移动端激活的搜索框
      volantis.$header.removeClass('z_search-open'); // 关闭移动端激活的搜索框
      volantis.$wrapper.removeClass('sub'); // 跳转页面时关闭二级导航

      // 解绑事件 避免重复监听
      volantis.$topBtn.unbind('click');
      $('.menu a').unbind('click');
      $(window).unbind('resize');
      $(window).unbind('scroll');
      $(document).unbind('scroll');
      $(document).unbind('click');
      $('body').unbind('click');
	  // 使用 volantis.pjax.send 方法传入pjax:send回调函数 参见layout/_partial/scripts/global.ejs
	  volantis.pjax.method.send.start();
    });

    document.addEventListener('pjax:complete', function () {
      $('.nav-main').find('.list-v').not('.menu-phone').removeAttr("style",""); // 移除小尾巴的移除
      $('.menu-phone.list-v').removeAttr("style",""); // 移除小尾巴的移除
      $('script[data-pjax], .pjax-reload script').each(function () {
        $(this).parent().append($(this).remove());
      });
      try{
		// 使用 volantis.pjax.push 方法传入重载函数 参见layout/_partial/scripts/global.ejs
		volantis.pjax.method.complete.start();
      } catch (e) {
        console.log(e);
      }
    });

    document.addEventListener('pjax:error', function (e) {
	  // 使用 volantis.pjax.error 方法传入pjax:error回调函数 参见layout/_partial/scripts/global.ejs
	  volantis.pjax.method.error.start();
      window.location.href = e.triggerElement.href;
    });
</script>
 
	  
    </div>
  </body>
</html>
